from typing import List
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        dp = [1] * n
        for i in range(1, n):
            m = 0
            for j in range(i):
                if nums[j] < nums[i]:
                    # print(m, dp[j])
                    # m = m+1
                    m = max(m, dp[j])
            dp[i] = m + 1
        print(dp)
        return max(dp)



if __name__ == "__main__":
    # list(range(0, 2500))
    # r = Solution().lengthOfLIS(list(range(0, 2500)))
    # r = Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])
    r = Solution().lengthOfLIS([1,3,6,7,9,4,10,5,6])
    print("r=", r)